package com.chj.jz.dp.class05;

public class Code12_BackpackII {
	/**
	 * @param m:
	 *            An integer m denotes the size of a backpack
	 * @param A:
	 *            Given n items with size A[i]
	 * @param V:
	 *            Given n items with value V[i]
	 * @return: The maximum value
	 */
	public static int backPackII(int m, int[] A, int[] V) {
		// write your code here

		int n = A.length;
		if (n == 0) {
			return 0;
		}

		int[][] f = new int[2][m + 1];
		int i, w;
		int old, now = 0;

		f[now][0] = 0;
		for (i = 1; i <= m; i++) {
			f[now][1] = -1;
		}

		for (i = 1; i <= n; i++) {
			old = now;
			now = 1 - now;
			for (w = 1; w <= m; w++) {
				f[now][w] = f[old][w];
				if (w >= A[i - 1] && f[old][w - A[i - 1]] != -1) {
					f[now][w] = Math.max(f[now][w], f[old][w - A[i - 1]] + V[i - 1]);
				}
			}
		}

		int res = 0;
		for (w = 0; w <= m; w++) {
			if (f[now][w] != -1) {
				res = Math.max(res, f[now][w]);
			}
		}

		return res;

	}
	
	 public static void main(String[] args) {
			{
				int[] arrK = new int[] {2, 3, 5, 7};
				int[] arrV = new int[] {1, 5, 2, 4};
				int k = 10;
				System.out.println(backPackII(k, arrK, arrV));
			}
			{
				int[] arrK = new int[] {2, 3, 8};
				int[] arrV = new int[] {2, 5, 8};
				int k = 10;
				System.out.println(backPackII(k, arrK, arrV));
			}
	    }
}
